package search.binary;

import java.util.ArrayList;
import java.util.List;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-04 12:42
 * @ Description :
 */
public class BinarySearch
{
    public static void main(String[] args)
    {
        int[] array = {1, 8, 10, 89, 1000, 1000, 1024};
        //int resIndex = binarySearch(array, 0, array.length - 1, 8);
        //System.out.println("resIndex = " + resIndex);
        System.out.println(multiBinarySearch(array, 0, array.length - 1, 1024));

    }

    public static int binarySearch(int[] array, int left, int right, int findVal)
    {
        if (left > right)
        {
            //没有找到
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = array[mid];

        if (findVal > midVal)
        {
            return binarySearch(array, mid + 1, right, findVal);
        }
        else if (findVal < midVal)
        {
            return binarySearch(array, left, mid - 1, findVal);
        }
        else
        {
            return mid;
        }
    }

    public static List<Integer> multiBinarySearch(int[] array, int left, int right, int findVal)
    {
        if (left > right)
        {
            //没有找到
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        int midVal = array[mid];

        if (findVal > midVal)
        {
            return multiBinarySearch(array, mid + 1, right, findVal);
        }
        else if (findVal < midVal)
        {
            return multiBinarySearch(array, left, mid - 1, findVal);
        }
        else
        {
            ArrayList<Integer> resIndexes = new ArrayList<>();

            int temp = mid - 1;
            while (temp >= 0 && array[temp] == findVal)
            {
                resIndexes.add(temp--);
            }

            resIndexes.add(mid);

            temp = mid + 1;
            while (temp <= array.length - 1 && array[temp] == findVal)
            {
                resIndexes.add(temp++);
            }

            return resIndexes;
        }
    }

}
